#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/7/19 11:09|11:09
# @Author  : yangdingyi
# @File    : 2020-07-19.5466.最多的不重叠子字符串
# @Software: PyCharm
from typing import List


class Solution:
    def maxNumOfSubstrings(self, s: str) -> List[str]:
        ans = []
        m = [[-1, -1, chr(ord('a')+i)] for i in range(26)]
        for si, ss in enumerate(s):
            a = ord(ss)-ord('a')
            if m[a][0] == -1:
                m[a][0] = si
                m[a][1] = si
            else:
                if si > m[a][1]:
                    m[a][1] = si
        mm = list(filter(lambda x: x[0] != -1, m))

        mm.sort(key=lambda x: x[0])
        print(m)
        ma = [mm[0]]
        lm = len(mm)
        lmi = 0
        for i in range(1, lm):
            if mm[i][0] <= ma[lmi][1]:
                ma[lmi][2] += mm[i][2]
                if mm[i][1] > ma[lmi][1]:
                    ma[lmi][1] = mm[i][1]
            else:
                ma.append(mm[i])
                lm += 1
                lmi += 1
        print(ma)

        return ans


solve = Solution()

questions = [
    ("adefaddaccc",),
    ("abbaccd",),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print(solve.maxNumOfSubstrings(q[0]))

